package es.ull.etsii.aa.datos;

import java.math.BigDecimal;
import java.util.Hashtable;
import java.util.LinkedList;

import es.ull.etsii.aa.metodos.GRASP;
import es.ull.etsii.aa.utiles.HashMatrix;
import es.ull.etsii.aa.utiles.ParIndice;

public class Ruta {

	public static final int TIPO_CAMION = 0;
	public static final int TIPO_MIXTO = 1;
	public static final int TIPO_VEHICULO = 2;

	private Nodo cola;
	private Nodo cabeza;

	private BigDecimal coste;

	private LinkedList<Nodo> camino;
	private LinkedList<Nodo> caminoDetallado;

	private Problema problema;

	private int tipo;

	/**
	 * Constructor de la clase Ruta.
	 * 
	 * @param problema
	 *            Problema asociado a la ruta.
	 * @param camino
	 *            Camino empleado por la ruta.
	 * @param cola
	 *            Cola de la ruta.
	 * @param cabeza
	 *            Cabeza de la ruta.
	 */
	public Ruta(Problema problema, LinkedList<Nodo> camino, Nodo cola,
			Nodo cabeza) {
		this.problema = problema;
		this.camino = camino;
		this.cabeza = cabeza;
		this.cola = cola;

		coste = new BigDecimal(0);
		coste.setScale(5, BigDecimal.ROUND_HALF_EVEN);

		caminoDetallado = new LinkedList<Nodo>();
	}

	/**
	 * Realiza una comprobacion de la viabilidad de la ruta.
	 * 
	 * @return True, si la ruta es viable. False, en caso contrario.
	 */
	public boolean esViable() {
		BigDecimal costeAux = new BigDecimal(0);
		costeAux.setScale(5, BigDecimal.ROUND_HALF_EVEN);

		int demandaTotal = 0;
		int nodosCamion = 0;

		// Calculo de coste total para TIPO_CAMION y TIPO_VEHICULO, demanda
		// total y numero de nodos de TIPO_CAMION.
		costeAux = costeAux.add(camino.get(0).distanciaEuclidea(camino.get(1)));

		for (int i = 1; i < camino.size() - 1; i++) {
			if (camino.get(i).getTipo() == Nodo.SOLO_CAMION)
				nodosCamion++;

			demandaTotal += camino.get(i).getDemanda();

			costeAux = costeAux.add(camino.get(i).distanciaEuclidea(
					camino.get(i + 1)));
		}

		// Ruta TIPO_CAMION
		if (demandaTotal <= problema.getCapacidadCamiones()) {
			tipo = TIPO_CAMION;
			coste = costeAux;
			caminoDetallado = camino;

			return true;
		}

		if (demandaTotal <= (problema.getCapacidadCamiones() + problema
				.getCapacidadTrailers())) {
			// Ruta TIPO_VEHICULO
			if (nodosCamion == 0) {
				tipo = TIPO_VEHICULO;
				coste = costeAux;
				caminoDetallado = camino;

				return true;
			}

			// Ruta TIPO_MIXTO
			tipo = TIPO_MIXTO;
			return esViableMixta();
		}

		return false;
	}

	/**
	 * Realiza una comprobacion de la viabilidad en caso de ser una ruta mixta.
	 * 
	 * @return True, si la ruta mixta es viable. False, en caso contrario.
	 */
	private boolean esViableMixta() {
		// El primer nodo del camino debe permitir la entrada de trailers
		if (camino.get(1).getTipo() == Nodo.SOLO_CAMION)
			return false;

		// Generacion de pares de nodos para el calculo de costes mixto
		LinkedList<ParIndice> listaIndices = new LinkedList<ParIndice>();

		for (int i = 1; i < camino.size() - 1; i++) {
			if (camino.get(i).getTipo() == Nodo.SOLO_CAMION)
				continue;

			for (int j = i; j < camino.size() - 1; j++) {
				listaIndices.add(new ParIndice(i, j));
			}
		}

		listaIndices.add(new ParIndice(0, 0));

		// Creacion de la tabla de costes y calculo del coste final
		HashMatrix<ParIndice, ParIndice, BigDecimal> tabla = calculaTablaCostes(listaIndices);
		return calculaCoste(tabla, listaIndices);
	}

	/**
	 * Calcula el coste final de la ruta.
	 * 
	 * @param tabla
	 *            Tabla de costes.
	 * @param listaIndices
	 *            Lista de nodos de la tabla de costes.
	 * @return True, si la ruta mixta es viable. False, en caso contrario.
	 */
	private boolean calculaCoste(
			HashMatrix<ParIndice, ParIndice, BigDecimal> tabla,
			LinkedList<ParIndice> listaIndices) {
		Hashtable<ParIndice, BigDecimal> columna = tabla.getColumn(listaIndices
				.getLast());

		// Si no se ha alcanzado el nodo final, la ruta es inviable.
		if (columna.isEmpty())
			return false;

//		for (ParIndice p1 : listaIndices) {
//			for (ParIndice p2 : listaIndices) {
//				if (tabla.get(p1, p2) == null)
//					System.out.print("-------- ");
//				else
//					System.out.print(tabla.get(p1, p2) + " ");
//			}
//
//			System.out.println();
//		}

		// Calculamos el minimo coste para alcanzar el nodo final.
		BigDecimal min = new BigDecimal(Integer.MAX_VALUE);
		min.setScale(5, BigDecimal.ROUND_HALF_EVEN);

		for (ParIndice pAux : listaIndices) {
			BigDecimal minAux = columna.get(pAux);

			if (minAux != null) {
				if (minAux.compareTo(min) == -1) {

					min = minAux;
				}
			}
		}
		
		coste = min;

		calculaCaminoDetallado(tabla, listaIndices);

		return true;
	}
	
	private void calculaCaminoDetallado(
			HashMatrix<ParIndice, ParIndice, BigDecimal> tabla,
			LinkedList<ParIndice> listaIndices) {
		Hashtable<ParIndice, BigDecimal> columna = tabla.getColumn(listaIndices
				.getLast());
		BigDecimal min = new BigDecimal(Integer.MAX_VALUE);
		min.setScale(5, BigDecimal.ROUND_HALF_EVEN);
		
		// Calculamos el camino detallado de la ruta
		caminoDetallado = new LinkedList<Nodo>();
		caminoDetallado.addFirst(camino.get(0));
		ParIndice parFinal = listaIndices.getFirst();
		ParIndice par = listaIndices.getLast();

		while(!parFinal.equals(par)) {
			for (ParIndice pAux : listaIndices) {
				BigDecimal minAux = columna.get(pAux);
	
				if (minAux != null) {
					if (minAux.compareTo(min) == -1) {
						par = pAux;
						min = minAux;
					}
				}
			}
			
			if (par.getIndice1() == par.getIndice2()) {
				if(!caminoDetallado.getFirst().equals(camino.get(par.getIndice1())))
					caminoDetallado.addFirst(camino.get(par.getIndice1()));
			}
			else {
				if(!caminoDetallado.getFirst().equals(camino.get(par.getIndice1())))
					caminoDetallado.addFirst(camino.get(par.getIndice1()));
				
				for( int i = par.getIndice2(); i >= par.getIndice1(); i--)
					caminoDetallado.addFirst(camino.get(i));
				
			}
			
			
			columna = tabla.getColumn(par);
		}
		
		caminoDetallado.addFirst(camino.get(0));
	}

	/**
	 * Calcula la tabla de costes asociada a una ruta.
	 * 
	 * @param listaIndices
	 *            Lista de nodos de la tabla de costes.
	 * @return Tabla de costes.
	 */
	private HashMatrix<ParIndice, ParIndice, BigDecimal> calculaTablaCostes(LinkedList<ParIndice> listaIndices) {
		HashMatrix<ParIndice, ParIndice, BigDecimal> tabla = new HashMatrix<ParIndice, ParIndice, BigDecimal>();

		int i = 1;
		int j = camino.size() - 2;

		tabla.put(listaIndices.get(0), listaIndices.get(0), camino.get(0).distanciaEuclidea(camino.get(1)));

		for (ParIndice p1 : listaIndices) {
			for (ParIndice p2 : listaIndices) {
				BigDecimal costeAux = null;

				int h = p1.getIndice1();
				int k = p1.getIndice2();
				int l = p2.getIndice1();
				int m = p2.getIndice2();
				
				// Subtour que sirve a clientes (k + 1, ..., m) dejando el
				// trailer en l.
				if ((h == l) && (i <= l) && (l <= j) &&
					(camino.get(l).getTipo() == Nodo.VEHICULO_COMPLETO) &&
					(k < m) && (m <= j) &&
					(calculaDemandaUM(k + 1, m) < problema.getCapacidadCamiones())) {
					costeAux = calculaCostesLKM(l, k + 1, m);
				}

				// Subtour que sirve a clientes
				if ((i <= h) && (h < l) && (l <= j)	&&
					(camino.get(h).getTipo() == Nodo.VEHICULO_COMPLETO)	&&
					(camino.get(l).getTipo() == Nodo.VEHICULO_COMPLETO)	&&
					(k == (l - 1)) && (k <= j) &&
					(calculaDemandaUM(k + 2, m) < problema.getCapacidadCamiones())) {
					costeAux = calculaCostesLKM(l, k + 1, m);
					costeAux = costeAux.add(camino.get(h).distanciaEuclidea(camino.get(l)));
				}

				// Subtour que lleva al cliente al nodo final
				if ((k == j) && p2.equals(listaIndices.getLast())) {
					costeAux = new BigDecimal(0);
					costeAux.setScale(5, BigDecimal.ROUND_HALF_EVEN);
					Nodo nodo1 = camino.get(p1.getIndice1());
					Nodo nodo2 = camino.get(p2.getIndice1());
					costeAux = costeAux.add(nodo1.distanciaEuclidea(
							nodo2));
				}

				if (costeAux != null) {
					Hashtable<ParIndice, BigDecimal> columna = tabla.getColumn(p1);

					BigDecimal min = new BigDecimal(Integer.MAX_VALUE);
					min.setScale(5, BigDecimal.ROUND_HALF_EVEN);

					for (ParIndice pAux : listaIndices) {
						BigDecimal minAux = columna.get(pAux);
						
						if (minAux != null) {
							if (minAux.compareTo(min) == -1) {
								min = minAux;
							}
						}
					}

					costeAux = costeAux.add(min);
					tabla.put(p1, p2, costeAux);
				}
			}
		}

		return tabla;
	}

	/**
	 * Calcula la demanda total de una subruta.
	 * 
	 * @param u
	 *            Indice del nodo inicial.
	 * @param m
	 *            Indice del nodo final.
	 * @return Demanda total.
	 */
	private int calculaDemandaUM(int u, int m) {
		int demandaTotal = 0;

		for (int i = u; i < m; i++)
			demandaTotal += camino.get(i).getDemanda();

		return demandaTotal;
	}

	/**
	 * Calcula el coste total de una subruta que usa el nodo con indice l como
	 * lugar donde dejar el trailer.
	 * 
	 * @param l
	 *            Indice del nodo en el que deja el trailer.
	 * @param k
	 *            Indice del nodo sucesor de l.
	 * @param m
	 *            Indice del nodo precedesor al retorno a l.
	 * @return Coste total
	 */
	private BigDecimal calculaCostesLKM(int l, int k, int m) {
		BigDecimal costeAux = new BigDecimal(0);
		costeAux.setScale(5, BigDecimal.ROUND_HALF_EVEN);

		costeAux = costeAux.add(camino.get(l).distanciaEuclidea(camino.get(k)));

		for (int i = k; i < m; i++)
			costeAux = costeAux.add(camino.get(i).distanciaEuclidea(
					camino.get(i + 1)));

		costeAux = costeAux.add(camino.get(m).distanciaEuclidea(camino.get(l)));

		return costeAux;
	}

	/**
	 * Retorna el nodo cabeza de la ruta.
	 * 
	 * @return Nodo cabeza.
	 */
	public Nodo getCabeza() {
		return cabeza;
	}

	/**
	 * Retorna el nodo cola de la ruta.
	 * @return Nodo cola.
	 */
	public Nodo getCola() {
		return cola;
	}

	/**
	 * Retorna el tipo de la ruta.
	 * 
	 * @return Tipo de la ruta.
	 */
	public int getTipo() {
		return tipo;
	}

	/**
	 * Retorna la cadena del tipo de la ruta.
	 * 
	 * @return Cadena del tipo de la ruta.
	 */
	public String getTipoString() {
		switch (tipo) {
		case TIPO_CAMION: 
			return "TIPO_CAMION";
		case TIPO_MIXTO:
			return "TIPO_MIXTO";
		case TIPO_VEHICULO:
			return "TIPO_VEHICULO";
		default:
			return "TIPO_DESCONOCIDO";
		}
	}
	
	/**
	 * Retorna el coste de la ruta.
	 * 
	 * @return Coste de la ruta.
	 */
	public BigDecimal getCoste() {
		return coste;
	}
	
	public LinkedList<Nodo> getCaminoDetallado() {
		return caminoDetallado;
	}
	
	public int getCamion() {
        return 1;
	}

	public int getTrailer() {
        return tipo==TIPO_VEHICULO||tipo==TIPO_MIXTO?1:0;
	}

	private LinkedList<Integer> tour2IntList(LinkedList<Nodo> tour) {
		LinkedList<Integer> ids = new LinkedList<Integer>();
		for (Nodo n : tour)
			ids.add(n.getId());
		return ids;
	}
	
	/**
	 * 
	 * @return identificadores del caminodetallado
	 */
	public LinkedList<Integer> getIntCaminoDetallado() {
		return tour2IntList(caminoDetallado);
	}
	
	/**
	 * @return Cadena de texto representativa de la Ruta
	 */
	public String toString() {
		String cadena = "";
		cadena += "Ruta(cola= " + cola.getId();
		cadena += ", cabeza=" + cabeza.getId();
		cadena += ", coste=" + coste.toString();
		cadena += ", tipo=" + getTipoString();
		cadena += ", camino=" + tour2IntList(camino).toString();
		cadena += ", caminoDetallado=" + getIntCaminoDetallado().toString();
		cadena += ")";
		return cadena;
	}
	
//	public String toString2() {
//		StringBuilder sb = new StringBuilder();
//
//		sb.append(this.getClass().getSimpleName() + "\n");
//		
//		switch (tipo) {
//		case TIPO_CAMION:
//			sb.append("\tTipo: TIPO_CAMION\n");			
//			break;
//		case TIPO_MIXTO:
//			sb.append("\tTipo: TIPO_MIXTO\n");
//			break;
//		case TIPO_VEHICULO:
//			sb.append("\tTipo: TIPO_VEHICULO\n");
//			break;
//		}
//		
//		sb.append("\tEstructura: " + caminoDetallado.get(0).getId());
//		
//		for(int i = 1; i < caminoDetallado.size(); i++)
//			sb.append("-" + caminoDetallado.get(i).getId());
//		
//		sb.append("\n");
//
//		sb.append("\tCoste: " + coste + "\n");
//		sb.append("\tCola: " + cola.getId() + "\n");
//		sb.append("\tCabeza: " + cabeza.getId() + "\n");
//
//
//		return sb.toString();
//	}
}
